#include <stdio.h>
#include <stdlib.h>
#include <queue>

using namespace std;
#define MaxSize 100

/*
二叉树的存储结构
*/

//顺序存储

struct TreeNode
{
    int value;
    bool isEmpty;
};

void InitTree(TreeNode t[MaxSize])
{
    for (int i = 0; i < MaxSize; i++)
    {
        t[i].isEmpty = true;
    }
}

//链式存储
typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

//先序遍历
void PreOrder(BiTree T)
{
    if (T != NULL)
    {
        printf("%d\t", T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//中序遍历
void InOrder(BiTree T)
{
    if (T != NULL)
    {
        InOrder(T->lchild);
        printf("%d\t", T->data);
        InOrder(T->rchild);
    }
}

//后序遍历
void PostOrder(BiTree T)
{
    if (T != NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%d\t", T->data);
    }
}

/*
层序遍历
根结点入队，
若队列非空，队头元素出队，将该结点的孩子入队
*/
void LevelOrder(BiTree T)
{
    queue<BiTNode *> q;
    BiTNode *p;
    q.push(T); //根结点入队
    while (!q.empty())
    {
        p = q.front();
        q.pop(); //出队队头元素
        printf("%d\t", p->data);
        if (p->lchild != NULL)
        {
            q.push(p->lchild);
        }
        if (p->rchild != NULL)
        {
            q.push(p->rchild);
        }
    }
}

int main()
{
    printf("\n\n========================================================================\n\n");

    //定义一棵树
    BiTree root = NULL;

    //插入根结点
    root = (BiTree)malloc(sizeof(BiTNode));
    root->data = 1;
    root->lchild = NULL;
    root->rchild = NULL;

    //插入新节点
    BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
    p->data = 2;
    p->lchild = NULL;
    p->rchild = NULL;
    root->lchild = p;

    LevelOrder(root);

    printf("\n\n========================================================================\n\n");
    return 0;
}